#include <iostream>
#include <set>
#include <map>
#include <list>

using namespace std;

struct Vertex
{
	size_t _id = 0;
	char _data = 0;
	std::set<size_t> _edges;

	void show(std::ostream& os) const;
};

struct BFSTree;
struct Graph
{
	std::map<size_t, Vertex> _vert;

	void addVertex(size_t id, char data);
	void addEdge(size_t id1, size_t id2);
	void addUEdge(size_t id1, size_t id2);
	bool calcBFS(BFSTree& tree) const;
	void show(std::ostream& os) const;
};

struct BFSTree
{
	const Graph* _pOwner = NULL;
	BFSTree* _pParent = NULL;
	size_t _id = 0;
	size_t _distance = 0;
	std::map<size_t, BFSTree> _cld;

	BFSTree() {}
	BFSTree(size_t id) { _id = id; }
	void show(std::ostream& os) const;
};

int main()
{
	Graph graph;
	graph.addVertex(1, 'r');
	graph.addVertex(2, 's');
	graph.addVertex(3, 't');
	graph.addVertex(4, 'u');
	graph.addVertex(5, 'v');
	graph.addVertex(6, 'w');
	graph.addVertex(7, 'x');
	graph.addVertex(8, 'y');
	graph.addUEdge(1, 2);
	graph.addUEdge(1, 5);
	graph.addUEdge(2, 6);
	graph.addUEdge(3, 6);
	graph.addUEdge(3, 7);
	graph.addUEdge(3, 4);
	graph.addUEdge(4, 7);
	graph.addUEdge(4, 8);
	graph.addUEdge(6, 7);
	graph.addUEdge(7, 8);
	graph.show(cout);

	BFSTree tree(2);
	graph.calcBFS(tree);
	tree.show(cout);

	return 0;
}

void Vertex::show(std::ostream& os) const
{
	os << "[" << _id << "]" << _data << ",{";
	bool first = true;
	for (auto i : _edges)
	{
		if (first) first = false;
		else os << ",";

		os << i;
	}
	os << "}";
}

void Graph::addVertex(size_t id, char data)
{
	Vertex& v = _vert[id];
	if (v._id)
		return;

	v._id = id;
	v._data = data;
}

void Graph::addEdge(size_t id1, size_t id2)
{
	auto it1 = _vert.find(id1);
	if (it1 == _vert.end())
		return;

	auto it2 = _vert.find(id2);
	if (it2 == _vert.end())
		return;

	it1->second._edges.insert(id2);
}

void Graph::addUEdge(size_t id1, size_t id2)
{
	auto it1 = _vert.find(id1);
	if (it1 == _vert.end())
		return;

	auto it2 = _vert.find(id2);
	if (it2 == _vert.end())
		return;

	it1->second._edges.insert(id2);
	it2->second._edges.insert(id1);
}

bool Graph::calcBFS(BFSTree& tree) const
{
	if (!tree._id)
		return false;

	auto vIt = _vert.find(tree._id);
	if (vIt == _vert.end())
		return false;

	std::map<size_t, BFSTree*> findMap;
		
	tree._pParent = NULL;
	tree._pOwner = this;
	tree._distance = 0;
	tree._cld.clear();
	findMap[tree._id] = &tree;

	std::list<const Vertex*> queue;
	queue.push_back(&vIt->second);
	while (queue.size())
	{
		const Vertex* pV = queue.front();
		queue.pop_front();

		auto treeIt = findMap.find(pV->_id);
		if (treeIt == findMap.end())
			continue;

		BFSTree* pTree = treeIt->second;
		for (auto i : pV->_edges)
		{
			auto tmpVIt = _vert.find(i);
			if (tmpVIt == _vert.end())
				continue;

			if (findMap.find(i) != findMap.end())
				continue;

			BFSTree& tmp = pTree->_cld[i];
			tmp._pParent = pTree;
			tmp._pOwner = this;
			tmp._distance = pTree->_distance + 1;
			tmp._id = i;
			findMap[i] = &tmp;
			queue.push_back(&tmpVIt->second);
		}
	}

	return true;
}

void Graph::show(std::ostream& os) const
{
	for (auto& pr : _vert)
	{
		pr.second.show(os);
		os << std::endl;
	}
}

void BFSTree::show(std::ostream& os) const
{
	if (!_pOwner)
	{
		os << "Error";
		return;
	}

	os << "[" << _id << "]";
	auto it = _pOwner->_vert.find(_id);
	if (it == _pOwner->_vert.end())
		os << "Null";
	else
		os << it->second._data;

	os << ",d=" << _distance;
	if (_cld.empty())
		return;

	bool first = true;
	os << ",{";
	for (auto& pr : _cld)
	{
		if (first) first = false;
		else os << ", ";

		pr.second.show(os);
	}

	os << "}";
}